#include "main/utils.h"
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
      unordered_map<int, int> mp;
      int majority = 0, cnt = 0;
      for (auto n : nums) {
        ++mp[n];
        if (mp[n] > cnt) {
          majority = n;
          cnt = mp[n];
        }
      }
      return majority;
    }

    int majorityElement1(vector<int>& nums) {
      sort(nums.begin(), nums.end());
      return nums[nums.size() / 2];
    }

    int majorityElement2(vector<int>& nums) {
      while (true) {
        int majority = nums[rand() % nums.size()];
        int cnt = 0;
        for (auto n : nums) {
          if (n == majority) {
            ++cnt;
          }
        }
        if (cnt > nums.size() / 2) {
          return majority;
        }
      }
    }

    int count_in_vec(vector<int>& nums, int target, int left, int right) {
      int cnt = 0;
      for (int i = left; i <= right; ++i) {
        if (nums[i] == target) {
          ++cnt;
        }
      }
      return cnt;
    }

    int majority_ele_rec(vector<int>& nums, int left, int right) {
      if (left == right) {
        return nums[left];
      }
      int mid = (right + left) / 2;
      int left_majority = majority_ele_rec(nums, left, mid);
      int right_majority = majority_ele_rec(nums, mid + 1, right);
      if (count_in_vec(nums, left_majority, left, right) > (right - left + 1) / 2) {
        return left_majority;
      }
      if (count_in_vec(nums, right_majority, left, right) > (right - left + 1) / 2) {
        return right_majority;
      }
      return -1;
    }

    int majorityElement3(vector<int>& nums) {
      return majority_ele_rec(nums, 0, nums.size() - 1);
    }

    int majorityElement4(vector<int>& nums) {
      int majority = -1;
      int cnt = 0;
      for (auto n : nums) {
        if (n == majority) {
          ++cnt;
        } else if (--cnt < 0) {
          majority = n;
          cnt = 1;
        }
      }
      return majority;
    }
};

int main() {
  vector<int> input = {3, 2, 3};
  Solution su;
  cout << su.majorityElement(input) << endl;
  cout << su.majorityElement1(input) << endl;
  cout << su.majorityElement2(input) << endl;
  cout << su.majorityElement3(input) << endl;
  cout << su.majorityElement4(input) << endl;
}
